package LC;

import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/n-queens-ii/description/
 * Follow up for N-Queens problem.
 * Now, instead outputting board configurations,
 * return the total number of distinct solutions.
 */
public class LC_052_NQueensII_Loop {
    public static void main(String[] args) {

    }

    static class Solution {

        public int totalNQueens(int n) {
            List<Integer> tmpList = new LinkedList<>();
            return solve(n, 0, tmpList);
        }

        private int solve(int n, int index, List<Integer> tmpList) {
            if (n == index) {
                return 1;
            }
            int count = 0;

            for (int col = 0; col < n; col++) {
                int rowList;
                for (rowList = 0; rowList < tmpList.size(); rowList++) {
                    int cobol = tmpList.get(rowList);
                    if (col == cobol)
                        break;
                    if (Math.abs(rowList - index) == Math.abs(cobol - col))
                        break;
                }
                if (rowList == tmpList.size()) {
                    tmpList.add(col);
                    int val = solve(n, index + 1, tmpList);
                    tmpList.remove(tmpList.size() - 1);
                    if (val > 0)
                        count += val;
                }
            }
            return count;
        }


    }

}
